1611F - ATM and Students - CodeForces Solution


binary search data structures two pointers *1800

Please click on ads to support us..

Python Code:

import sys
sys.stdin.readline
tc = int(input())
 
 
for _ in range(tc):
    n, k = map(int, input().split())
    ar = list(map(int, input().split()))
    ans= 0
    l = 0
    r = 0
    sum = k
    maxd = 0
    resL = -1
    resr = -1
    
    while r <= len(ar) - 1:
        sum += ar[r]
        if sum < 0:
            r += 1
            while l < r and  sum < 0:
                sum -= ar[l]
                l += 1
            
        else:
            dist = (r - l) + 1
            
            if maxd < dist: 
                resL = l + 1
                resr = r + 1
                maxd = max(maxd, dist)
            r += 1
    if resL == -1:
        print(-1)
    else:
        print(resL, resr)

C++ Code:

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define EB emplace_back
#define MP make_pair
#define alli(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define fr(i,n) for(lli i=0;i<(n);++i)
#define rep(i,a,b) for(lli i=a;i<=b;++i)
#define per(i,a,b) for(lli i=a;i>=b;i--)
#define remin(a,b) (a=min((a),(b)))
#define remax(a,b) (a=max((a),(b)))
#define sz(x) (lli)(x).size()
#define endl '\n'
typedef long long lli;        typedef long double ld;
typedef pair<lli, lli> ii;     typedef vector<lli> vi;
typedef vector<ii> vii;       typedef vector<vi> graph;
long long MOD = 1000000007;
long double EPS = 1e-9;
#define inf 1000000000000000005
// long long MOD = 998244353;
#define sqrt(x) sqrtl(x)
//-----
lli inv(lli i) {if (i == 1) return 1; return (MOD - ((MOD / i) * inv(MOD % i)) % MOD) % MOD;}

lli MOD_mul(lli a, lli b) {a = a % MOD; b = b % MOD; return (((a * b) % MOD) + MOD) % MOD;}

lli MOD_add(lli a, lli b) {a = a % MOD; b = b % MOD; return (((a + b) % MOD) + MOD) % MOD;}

lli gcd(lli a, lli b) { if (b == 0) return a; return gcd(b, a % b);}

lli ceil_div(lli a, lli b) {return a % b == 0 ? a / b : a / b + 1;}

lli pwr(lli a, lli b) {a %= MOD; lli res = 1; while (b > 0) {if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1;} return res;}

// bool comparefn(pair<ld, lli> a, pair<ld, lli> b)
// {
// 	if (a.F == b.F) {
// 		return a.S <= b.S;
// 	}

// 	return a.F > b.F;
// }
//----------------

vector<int> d = { -1, 0, 1, 0, -1};
vector<char> di = {'U', 'R', 'D', 'L'};
// vector<vector<lli>> g;
vector<vector<lli>> f;
// vector<lli> vis;
vector<lli> dist;
vector<int> par;
vector<lli> v;
lli n, m, k;
lli x;
set<lli> all;
vector<lli> pre;
lli ok;



void solve() {
	cin >> n >> x;

	vi a(n);
	fr(i, n) {
		cin >> a[i];
	}

	lli len = 0;
	ii ans = { -1, -1};
	lli i = 0, st = 0;
	while (i < n) {
		x += a[i];
		if (i - st + 1 > len && x >= 0) {
			len = i - st + 1;
			ans.F = st;
			ans.S = i;
		} else {
			while (x < 0) {
				x -= a[st];
				st++;
			}

			if (i - st + 1 > len && x >= 0) {
				len = i - st + 1;
				ans.F = st;
				ans.S = i;
			}
		}
		i++;
	}

	if (len == 0) {
		cout << -1 << endl;
	} else {
		cout << ans.F + 1LL << " " << ans.S + 1LL << endl;
	}
}



int main() {
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;
	cout << setprecision(15);

	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}




Comments

Submit
0 Comments
More Questions

365A - Good Number
1204B - Mislove Has Lost an Array
1409D - Decrease the Sum of Digits
1476E - Pattern Matching
1107A - Digits Sequence Dividing
1348A - Phoenix and Balance
1343B - Balanced Array
1186A - Vus the Cossack and a Contest
1494A - ABC String
1606A - AB Balance
1658C - Shinju and the Lost Permutation
1547C - Pair Programming
550A - Two Substrings
797B - Odd sum
1093A - Dice Rolling
1360B - Honest Coach
1399C - Boats Competition
1609C - Complex Market Analysis
1657E - Star MST
1143B - Nirvana
1285A - Mezo Playing Zoma
919B - Perfect Number
894A - QAQ
1551A - Polycarp and Coins
313A - Ilya and Bank Account
1469A - Regular Bracket Sequence
919C - Seat Arrangements
1634A - Reverse and Concatenate
1619C - Wrong Addition
1437A - Marketing Scheme